Signal processing is an important function of many electronic systems. In particular, in many electronic systems, data is transmitted in signal form. Further, some electronic systems analyze and monitor the operation of mechanical or chemical systems by observing the characteristics of signals, such as vibration signals and other types of signals, that are output from these systems. In light of this, methods have been developed to characterize signals such that information or data in the signal is available for data processing.
As one example, in many electronic systems, time domain signals are typically transformed to the frequency domain prior to signal processing. A typical method for converting signals to the frequency domain is performed using Fourier Transforms. The Fourier Transform of a signal is based on a plurality of samples of the time domain signal taken over a selected time period, known as the base frequency. Based on these samples of the signal the Fourier Transform provides a plurality of coefficients, where the coefficients respectively represent the amplitude of a frequency that is a multiple of the base frequency. These coefficients of the Fourier Transform, which represent the signal in the frequency domain, are then used by electronic systems in processing the signal.
Although Fourier Transforms are among some of the most widely used functions for processing signals, there are other functions that are either currently used or will be used in the future, as a better understanding of their applicability is recognized. These functions include Bessel functions, Legendre Polynomials, Tschebysheff Polynomials of First and Second Kind, Jacoby Polynomials, Generalized Laguerre Polynomials, Hermite Polynomials, Bernoulli Polynomials, Euler Polynomials, and a variety of Matrices used in Quantum Mechanics, Linear Analysis functions, wavelets and fractals just to name a few.
Although Fourier transforms and the other functions mentioned above are useful in determining characteristics of signals for use in data processing, there are some drawbacks to their use. Specifically, application of these functions to signals is typically computationally intensive. This is disadvantageous as it may require the use of specialized processors in order to perform data processing. Further, and even more importantly, the time required to perform the number of computations using these functions may cause an unacceptable delay for many data processing applications. In fact, a goal of many data processing systems is the ability to process data signals in real time, with no delay.
For example, the Fourier Series is defined as an infinite series of coefficients representing a signal. To transform a signal using a Fourier Series would require an infinite number of computations. To remedy this problem, many conventional data processing systems use Discrete Fourier Transforms (DFT), as opposed to the infinite Fourier Series. The DFT is the digital approximation to the Fourier Series and is used to process digitized analog information. Importantly, the DFT replaces the infinite series of the Fourier Series with a finite set of N evenly spaced samples taken over a finite period. The computation of the DFT therefore provides the same number of coefficients as the samples received, instead of an infinite number of samples required by the Fourier Series. As such, use of the DFT provides the most satisfactory current means to process the signal.
Because of the importance of reducing the time required to process signals, however, methods have been developed to further reduce the number of computations required to perform a DFT of a signal. Specifically, the DFT procedure computes each coefficient by a similar process. The process for a general coefficient is; multiply each sample by the sine or cosine of the normalized value of the independent variable times the angular rate and sum over all of the samples. This procedure defines N multiply-add steps for each of N coefficients, which in turn, equates to N2 multiply-add computations per DFT. As many samples of a signal are typically required to perform an adequate approximation of the signal, the DFT of a signal is typically computational and time intensive.
One of the methods developed to reduce the number of computations is the butterfly method, which reduces the number of computations from N2 to N times log(N). The butterfly method is based on the fact that many of the trigonometric values of the DFT are the same due to periodicity of the functions. As such, the butterfly method reduces the matrix associated with the DFT into N/2 two-point transforms (i.e., the transforms representing each coefficient an and bn). The butterfly method further reduces the redundant trigonometric values of the DFT. Although the butterfly method reduces the number of computations over the more traditional DFT method, it also adds complexity to the Fourier transformation of a signal. Specifically, the butterfly method uses a complex method for addressing the samples of the signal and the matrix containing the functions. This complexity can require the use of specialized processors and increase time for computation of the Fourier Transform. By its nature, the butterfly is a batch process, which does not begin determination of the coefficients until after all of the samples have been received. As described later, this method causes latency in the determination of the coefficients of the function.
An additional problem with the DFT, besides the number of computations required, is that the value of each coefficient of the DFT is a function of all the samples of the signal. Therefore, none of the coefficients of the DFT can be determined until all of the samples have been processed. Once the last sample of a set is received, the values of all of the coefficients can then be defined. As such, the time between the arrival of the last sample and the availability of the coefficients is referred to as the latency of the system. If the time for processing the coefficients is greater than the time to collect the set of samples, the system cannot operate in real time.
Although no coefficient is defined until all of the samples have been received, there is an advantageous property of the DFT that has not been heretofore recognized in the prior art. This property is the independence of samples. In a set of samples being transformed in a DFT process, each sample makes a contribution to each coefficient based only on the sine or cosine of the applicable angle. This is illustrated in Appendix 1. Specifically, each of the coefficients of the DFT, (i.e., A0, A1, A2, . . . and B0, B1, B2, . . . ), is the summation of the application of each sample to the sine and cosine functions associated with each coefficient. For example, the coefficient A1 is the summation A11+A12+ . . . A18, which are the application of each sample to the cosine function associated with the A1 coefficient. As each of the samples are related to each coefficient by addition, each sample is independent of the other samples and can be used to update the coefficients prior to receipt of the other samples.
Many conventional systems for determining the Fourier Transform of a signal do not recognize this independence of samples aspect of the DFT. Specifically, conventional systems that use the DFT typically first receive a number of samples N of a signal, and only after all of the samples have been received does the system generate each of the coefficients. As such, these conventional systems have an associated latency equal to the time required for the system to compute each of the coefficients after the last sample is received. This latency may be significant. For example, if a conventional system determines a DFT using N=64 samples, then the number of computations is N2 or 4096. For the Fast Fourier Transform (FFT), this is reduced to N times log(N) or 64(6) equals 364.
Appendix 1 illustrates an example of a data processing system that waits until all of the samples have been received prior to determining the coefficients of the DFT. As can be seen, the data processing system illustrated in Appendix 1, first receives eight samples of the signal prior to beginning to process any of the coefficients of the Fourier Transform. Only after receipt of the samples does the system begin to calculate the coefficients. As latency is defined as the time between the receipt of the last sample and the time at which the coefficients are available, this data processing system has latency equal to the time required to perform all computations of the coefficients. As such, this data processing system cannot be used for real-time data processing. As real-time data processing or approximate real-time data processing is advantageous for use in many data processing systems, it would be desirous to provide apparatus and methods that decrease the time required to perform transformation of signals.
An additional problem with many conventional data processing systems, such as the butterfly, is that the coefficients of the function cannot be independently observed due to the complexity of the system. Further, because the butterfly determines the coefficients in a batch method, as opposed to real time, individual coefficients can not be observed and tracked as each new sample is received. Because, the batch method of analysis adds latency, considerable processing must be employed with conventional systems to observe and track coefficients over time. Observance and tracking individual coefficients of a signal is advantageous for in-depth signal analysis.
A still further problem with many conventional data processing systems is that these systems typically do allow for variation of the resolution of individual coefficients of the function. For example, the butterfly is configured to calculate each coefficient producing the same number coefficients as of samples. This may be disadvantageous in applications in which there is interest in only one or a subset of the coefficients, as the butterfly will spend time and resources determining coefficients of less importance to the same resolution as those coefficients of importance. In light of this, it would be desirous to provide apparatus and methods that allow for the tracking and observance of individual coefficients and also varying the resolution with which individual coefficients are calculated.